Various systems, such as data communication systems and data processing systems, transfer digital data. Examples of data transfers include a transmission of data from a source location to a remote location within a communication system, and a storage/retrieval cycle of data within a processing system. Various influences can cause corruption of the data. For example, communication systems often transmit data across great distances through the atmosphere. Atmospheric conditions, such as lightning, can disrupt the data signal.
Various techniques have been developed for increasing the probability of error free data transfer. One example technique is based upon the inclusion of error correction data with the information (i.e., the original) data to provide error correction code words. Correction of erroneous information data at the destination (e.g., upon receipt or retrieval) is possible by mathematically reconstituting correct code words. To construct a code word, error correction data, often referred to as parity, is derived from the original data. The parity, in essence, mathematically characterizes the pattern of the original data. Upon receipt or retrieval, a decoder, using the parity, examines and manipulates the data in a fashion to detect, locate, and correct errors which have occurred therein.
A particular error detecting and correcting technique is directed to algebraic block codes wherein binary numbers are utilized to represent elements in a finite or Galois Field. A Galois Field (2.sup.M) has 2.sup.M elements, in which each element is M bits in length. The Galois Field elements may be considered as binary vectors representing data words or "symbols". Typically, such Galois Field elements are multiplied in processes used to encode and decode messages for error correction purposes. Galois Field multiplication is fundamental in algebraic code techniques, but usually involves complicated operations. Some known Galois Field multipliers are decidedly too complex or too specialized, and thus of limited capability.
Modern data systems transfer a relatively large amount of data in a relatively short period of time. The modern systems have large data throughput, and thus have high error correction requirements. For example, television transmission systems which operate within the advanced television system standard (hereinafter referred to as "ATSS") require a Reed-Solomon encoder utilizing Galois Field type error correction. The typical Reed-Solomon encoder operating within the ATSS must accept 187 eight-bit bytes of information data and generate 20 eight-bit bytes of error correction data (i.e., parity). To accomplish this requires a lengthy polynomial multiplication sequence as well as significant growth in signal data rate. Some known Galois Field multipliers are relatively slow and, as a result, may be unable to operate at the speed necessary to support the required data rates.